/*
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

/*
 *
 *
 *
 *
 *
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

package java.util.concurrent.locks;
import java.util.concurrent.TimeUnit;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Date;
import sun.misc.Unsafe;

/**
 * Provides a framework for implementing blocking locks and related
 * synchronizers (semaphores, events, etc) that rely on
 * first-in-first-out (FIFO) wait queues.  This class is designed to
 * be a useful basis for most kinds of synchronizers that rely on a
 * single atomic {@code int} value to represent state. Subclasses
 * must define the protected methods that change this state, and which
 * define what that state means in terms of this object being acquired
 * or released.  Given these, the other methods in this class carry
 * out all queuing and blocking mechanics. Subclasses can maintain
 * other state fields, but only the atomically updated {@code int}
 * value manipulated using methods {@link #getState}, {@link
 * #setState} and {@link #compareAndSetState} is tracked with respect
 * to synchronization.
 *
 * <p>Subclasses should be defined as non-public internal helper
 * classes that are used to implement the synchronization properties
 * of their enclosing class.  Class
 * {@code AbstractQueuedSynchronizer} does not implement any
 * synchronization interface.  Instead it defines methods such as
 * {@link #acquireInterruptibly} that can be invoked as
 * appropriate by concrete locks and related synchronizers to
 * implement their public methods.
 *
 * <p>This class supports either or both a default <em>exclusive</em>
 * mode and a <em>shared</em> mode. When acquired in exclusive mode,
 * attempted acquires by other threads cannot succeed. Shared mode
 * acquires by multiple threads may (but need not) succeed. This class
 * does not &quot;understand&quot; these differences except in the
 * mechanical sense that when a shared mode acquire succeeds, the next
 * waiting thread (if one exists) must also determine whether it can
 * acquire as well. Threads waiting in the different modes share the
 * same FIFO queue. Usually, implementation subclasses support only
 * one of these modes, but both can come into play for example in a
 * {@link ReadWriteLock}. Subclasses that support only exclusive or
 * only shared modes need not define the methods supporting the unused mode.
 *
 * <p>This class defines a nested {@link ConditionObject} class that
 * can be used as a {@link Condition} implementation by subclasses
 * supporting exclusive mode for which method {@link
 * #isHeldExclusively} reports whether synchronization is exclusively
 * held with respect to the current thread, method {@link #release}
 * invoked with the current {@link #getState} value fully releases
 * this object, and {@link #acquire}, given this saved state value,
 * eventually restores this object to its previous acquired state.  No
 * {@code AbstractQueuedSynchronizer} method otherwise creates such a
 * condition, so if this constraint cannot be met, do not use it.  The
 * behavior of {@link ConditionObject} depends of course on the
 * semantics of its synchronizer implementation.
 *
 * <p>This class provides inspection, instrumentation, and monitoring
 * methods for the internal queue, as well as similar methods for
 * condition objects. These can be exported as desired into classes
 * using an {@code AbstractQueuedSynchronizer} for their
 * synchronization mechanics.
 *
 * <p>Serialization of this class stores only the underlying atomic
 * integer maintaining state, so deserialized objects have empty
 * thread queues. Typical subclasses requiring serializability will
 * define a {@code readObject} method that restores this to a known
 * initial state upon deserialization.
 *
 * <h3>Usage</h3>
 *
 * <p>To use this class as the basis of a synchronizer, redefine the
 * following methods, as applicable, by inspecting and/or modifying
 * the synchronization state using {@link #getState}, {@link
 * #setState} and/or {@link #compareAndSetState}:
 *
 * <ul>
 * <li> {@link #tryAcquire}
 * <li> {@link #tryRelease}
 * <li> {@link #tryAcquireShared}
 * <li> {@link #tryReleaseShared}
 * <li> {@link #isHeldExclusively}
 * </ul>
 * <p>
 * Each of these methods by default throws {@link
 * UnsupportedOperationException}.  Implementations of these methods
 * must be internally thread-safe, and should in general be short and
 * not block. Defining these methods is the <em>only</em> supported
 * means of using this class. All other methods are declared
 * {@code final} because they cannot be independently varied.
 *
 * <p>You may also find the inherited methods from {@link
 * AbstractOwnableSynchronizer} useful to keep track of the thread
 * owning an exclusive synchronizer.  You are encouraged to use them
 * -- this enables monitoring and diagnostic tools to assist users in
 * determining which threads hold locks.
 *
 * <p>Even though this class is based on an internal FIFO queue, it
 * does not automatically enforce FIFO acquisition policies.  The core
 * of exclusive synchronization takes the form:
 *
 * <pre>
 * Acquire:
 *     while (!tryAcquire(arg)) {
 *        <em>enqueue thread if it is not already queued</em>;
 *        <em>possibly block current thread</em>;
 *     }
 *
 * Release:
 *     if (tryRelease(arg))
 *        <em>unblock the first queued thread</em>;
 * </pre>
 * <p>
 * (Shared mode is similar but may involve cascading signals.)
 *
 * <p id="barging">Because checks in acquire are invoked before
 * enqueuing, a newly acquiring thread may <em>barge</em> ahead of
 * others that are blocked and queued.  However, you can, if desired,
 * define {@code tryAcquire} and/or {@code tryAcquireShared} to
 * disable barging by internally invoking one or more of the inspection
 * methods, thereby providing a <em>fair</em> FIFO acquisition order.
 * In particular, most fair synchronizers can define {@code tryAcquire}
 * to return {@code false} if {@link #hasQueuedPredecessors} (a method
 * specifically designed to be used by fair synchronizers) returns
 * {@code true}.  Other variations are possible.
 *
 * <p>Throughput and scalability are generally highest for the
 * default barging (also known as <em>greedy</em>,
 * <em>renouncement</em>, and <em>convoy-avoidance</em>) strategy.
 * While this is not guaranteed to be fair or starvation-free, earlier
 * queued threads are allowed to recontend before later queued
 * threads, and each recontention has an unbiased chance to succeed
 * against incoming threads.  Also, while acquires do not
 * &quot;spin&quot; in the usual sense, they may perform multiple
 * invocations of {@code tryAcquire} interspersed with other
 * computations before blocking.  This gives most of the benefits of
 * spins when exclusive synchronization is only briefly held, without
 * most of the liabilities when it isn't. If so desired, you can
 * augment this by preceding calls to acquire methods with
 * "fast-path" checks, possibly prechecking {@link #hasContended}
 * and/or {@link #hasQueuedThreads} to only do so if the synchronizer
 * is likely not to be contended.
 *
 * <p>This class provides an efficient and scalable basis for
 * synchronization in part by specializing its range of use to
 * synchronizers that can rely on {@code int} state, acquire, and
 * release parameters, and an internal FIFO wait queue. When this does
 * not suffice, you can build synchronizers from a lower level using
 * {@link java.util.concurrent.atomic atomic} classes, your own custom
 * {@link java.util.Queue} classes, and {@link LockSupport} blocking
 * support.
 *
 * <h3>Usage Examples</h3>
 *
 * <p>Here is a non-reentrant mutual exclusion lock class that uses
 * the value zero to represent the unlocked state, and one to
 * represent the locked state. While a non-reentrant lock
 * does not strictly require recording of the current owner
 * thread, this class does so anyway to make usage easier to monitor.
 * It also supports conditions and exposes
 * one of the instrumentation methods:
 *
 *  <pre> {@code
 * class Mutex implements Lock, java.io.Serializable {
 *
 *   // Our internal helper class
 *   private static class Sync extends AbstractQueuedSynchronizer {
 *     // Reports whether in locked state
 *     protected boolean isHeldExclusively() {
 *       return getState() == 1;
 *     }
 *
 *     // Acquires the lock if state is zero
 *     public boolean tryAcquire(int acquires) {
 *       assert acquires == 1; // Otherwise unused
 *       if (compareAndSetState(0, 1)) {
 *         setExclusiveOwnerThread(Thread.currentThread());
 *         return true;
 *       }
 *       return false;
 *     }
 *
 *     // Releases the lock by setting state to zero
 *     protected boolean tryRelease(int releases) {
 *       assert releases == 1; // Otherwise unused
 *       if (getState() == 0) throw new IllegalMonitorStateException();
 *       setExclusiveOwnerThread(null);
 *       setState(0);
 *       return true;
 *     }
 *
 *     // Provides a Condition
 *     Condition newCondition() { return new ConditionObject(); }
 *
 *     // Deserializes properly
 *     private void readObject(ObjectInputStream s)
 *         throws IOException, ClassNotFoundException {
 *       s.defaultReadObject();
 *       setState(0); // reset to unlocked state
 *     }
 *   }
 *
 *   // The sync object does all the hard work. We just forward to it.
 *   private final Sync sync = new Sync();
 *
 *   public void lock()                { sync.acquire(1); }
 *   public boolean tryLock()          { return sync.tryAcquire(1); }
 *   public void unlock()              { sync.release(1); }
 *   public Condition newCondition()   { return sync.newCondition(); }
 *   public boolean isLocked()         { return sync.isHeldExclusively(); }
 *   public boolean hasQueuedThreads() { return sync.hasQueuedThreads(); }
 *   public void lockInterruptibly() throws InterruptedException {
 *     sync.acquireInterruptibly(1);
 *   }
 *   public boolean tryLock(long timeout, TimeUnit unit)
 *       throws InterruptedException {
 *     return sync.tryAcquireNanos(1, unit.toNanos(timeout));
 *   }
 * }}</pre>
 *
 * <p>Here is a latch class that is like a
 * {@link java.util.concurrent.CountDownLatch CountDownLatch}
 * except that it only requires a single {@code signal} to
 * fire. Because a latch is non-exclusive, it uses the {@code shared}
 * acquire and release methods.
 *
 *  <pre> {@code
 * class BooleanLatch {
 *
 *   private static class Sync extends AbstractQueuedSynchronizer {
 *     boolean isSignalled() { return getState() != 0; }
 *
 *     protected int tryAcquireShared(int ignore) {
 *       return isSignalled() ? 1 : -1;
 *     }
 *
 *     protected boolean tryReleaseShared(int ignore) {
 *       setState(1);
 *       return true;
 *     }
 *   }
 *
 *   private final Sync sync = new Sync();
 *   public boolean isSignalled() { return sync.isSignalled(); }
 *   public void signal()         { sync.releaseShared(1); }
 *   public void await() throws InterruptedException {
 *     sync.acquireSharedInterruptibly(1);
 *   }
 * }}</pre>
 *
 * @author Doug Lea
 * @since 1.5
 */
public abstract class AbstractQueuedSynchronizer
        extends AbstractOwnableSynchronizer
        implements java.io.Serializable {

    private static final long serialVersionUID = 7373984972572414691L;

    protected AbstractQueuedSynchronizer() {
    }

    /**
     * 不管是同步队列还是条件队列都是基于Node类
     *
     * 同步队列：也称CLH队列，是Craig、Landin、Hagers 发明的一种FIFO双向链表队列，此CLH队列是原CLH的变种，
     * 由原来的不断自旋改为了阻塞机制。队列中有头节点和尾节点两个指针，尾节点就是指向最后一个节点，而头节点为了便于判断，
     * 永远指向一个空节点，之后才是第一个有数据的节点；
     *
     * 条件队列：能够使某些线程一起等待某个条件具备时，才会被唤醒，唤醒后会被放到CLH队列中重新争夺锁资源。
     */
    static final class Node {
        /**
         * 标识节点为共享模式
         */
        static final Node SHARED = new Node();
        /**
         * 标识节点为独占模式
         */
        static final Node EXCLUSIVE = null;
        /**
         * 标识当前节点已被取消
         * 当前线程因为超时或者中断被取消，这是一个终结态
         */
        static final int CANCELLED = 1;
        /**
         * 标识当前节点的后继节点被阻塞或即将被阻塞
         * 当前节点的后继线程被阻塞或者即将被阻塞，当前线程释放锁或者取消后需要唤醒后继线程，该状态一般都是后继线程来设置前驱节点的。
         */
        static final int SIGNAL = -1;
        /**
         * 标识当前节点在条件队列中，正在等待条件
         * 节点在条件队列中，节点的线程等待在Condition上，当其他线程对Condition调用了signal()方法后，该节点会从条件队列中转移到同步队列中，加入到同步状态的获取中
         */
        static final int CONDITION = -2;
        /**
         * 用于将唤醒后继线程的动作传递下去，这个状态的引入是为了完善和增强共享锁的唤醒机制。在一个节点成为头节点之前，是不会跃迁为此状态的
         */
        static final int PROPAGATE = -3;
        /**
         * 标记当前节点的信号量状态 (1,0,‐1,‐2,‐3)5种状态  初始状态0
         * 使用CAS更改状态，volatile保证线程可见性
         */
        volatile int waitStatus;
        /**
         * 前驱节点（同步队列）
         */
        volatile Node prev;
        /**
         * 后继节点（同步队列）
         */
        volatile Node next;
        /**
         * 当前节点对应的线程
         */
        volatile Thread thread;
        /**
         * 条件队列中用来表示下一个节点
         */
        Node nextWaiter;

        /**
         * 如果节点在共享模式下等待，则返回 true。
         */
        final boolean isShared() {
            return nextWaiter == SHARED;
        }

        /**
         * 返回前驱节点
         */
        final Node predecessor() throws NullPointerException {
            Node p = prev;
            if (p == null)
                throw new NullPointerException();
            else
                return p;
        }

        /**
         * 创建同步队列头节点或用于标记共享模式
         */
        Node() {    // Used to establish initial head or SHARED marker
        }

        /**
         * 用于同步队列
         */
        Node(Thread thread, Node mode) {     // Used by addWaiter
            this.nextWaiter = mode;
            this.thread = thread;
        }

        /**
         * 用于条件队列
         */
        Node(Thread thread, int waitStatus) { // Used by Condition
            this.waitStatus = waitStatus;
            this.thread = thread;
        }
    }

    /**
     * 同步队列的头节点
     */
    private transient volatile Node head;
    /**
     * 同步队列的尾节点
     */
    private transient volatile Node tail;
    /**
     * 同步资源状态
     */
    private volatile int state;

    protected final int getState() {
        return state;
    }

    /**
     * 更新State
     */
    protected final void setState(int newState) {
        state = newState;
    }

    /**
     * CAS更新State
     */
    protected final boolean compareAndSetState(int expect, int update) {
        // See below for intrinsics setup to support this
        return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
    }

    // Queuing utilities

    /**
     * 自旋的纳秒数（尽量不让线程挂起）
     */
    static final long spinForTimeoutThreshold = 1000L;

    /**
     * 节点加入同步队列(返回的是前驱节点)
     */
    private Node enq(final Node node) {
        for (;;) {
            //获取最新的尾部节点
            Node t = tail;
            //队列为空需要初始化，创建空的头节点
            if (t == null) { // Must initialize
                if (compareAndSetHead(new Node()))
                    //头结点和尾节点指向刚刚初始化的节点
                    tail = head;
            } else {
                //把当前的尾部节点设置为当前节点的前驱节点（无需CAS设置）
                node.prev = t;
                //CAS设置自己为新的尾部节点
                if (compareAndSetTail(t, node)) {
                    //设置原尾部节点的后继节点为当前节点
                    //（此处请加以重视-->当锁资源被释放后唤醒后继节点时是从尾部节点向前找节点进行唤醒的，那时你会理解）
                    t.next = node;
                    return t;
                }
            }
        }
    }

    /**
     * 将当前节点入队（有队入队，无队初始化队列后入队）
     */
    private Node addWaiter(Node mode) {
        //将当前线程构建成Node类型（此时当前节点的waitStatus=0）
        Node node = new Node(Thread.currentThread(), mode);
        //李二狗认为一般来说，快速入队是容易成功的。（队列已经存在且设置自己为尾部节点不容易失败）
        //获取最新的尾部节点
        Node pred = tail;
        //尾部节点存在
        if (pred != null) {
            //把当前的尾部节点设置为当前节点的前驱节点（无需CAS设置）
            node.prev = pred;
            //CAS设置自己为新的尾部节点
            if (compareAndSetTail(pred, node)) {
                //（此处请加以重视-->当锁资源被释放后唤醒后继节点时是从尾部节点向前找节点进行唤醒的，那时你会理解）
                pred.next = node;
                return node;
            }
        }
        enq(node);
        return node;
    }

    /**
     * 设置当前节点为头节点（仅可从acquire处调用而来）
     */
    private void setHead(Node node) {
        //设置当前节点为头结点
        head = node;
        //设置当前节点关联的线程为null
        node.thread = null;
        //断开与原头结点的关联（但此时原头结点的下一个节点仍记录着当前节点）
        node.prev = null;
    }

    /**
     * 唤醒节点的后继节点（如果存在）
     */
    private void unparkSuccessor(Node node) {
        /*
         * If status is negative (i.e., possibly needing signal) try
         * to clear in anticipation of signalling.  It is OK if this
         * fails or if status is changed by waiting thread.
         * 如果状态为负数（即，可能需要信号），尝试在信号之前清除。如果这一步失败或者状态被等待的线程改变也是可以的。
         */
        int ws = node.waitStatus;
        if (ws < 0)
            //允许失败
            compareAndSetWaitStatus(node, ws, 0);

        /*
         * 需要唤醒的节点，通常是下一个节点。
         * 如果后继节点被取消或明显为空，则从尾部向前遍历以找到实际的未取消的距离当前节点最近的后继节点。
         * 1.后续节点被取消：很好理解,不做解释
         * 2.后续节点为空：当前节点是在执行 Node s = node.next 的时候是尾部节点
         *
         * 问：为什么需要从尾部向前找距离当前节点最近的未被取消的后继节点？
         * 答案：问题出在enq操作，当CAS设置自己为新的尾部节点成功时,
         * 老的尾部节点可能还未来得及设置最新的尾部节点为自己的后继节点
         *
         * 问：下一个节点为空为什么还要去从尾部向前找节点？
         * 答案：判断下一个节点为空的瞬间队列中确实没有节点，但可能该节点已经不是尾部节点了，需要唤醒刚入到CLH队列的等待节点
         */
        Node s = node.next;
        // 下一个节点为空 或者 不为空，但是被取消了
        if (s == null || s.waitStatus > 0) {
            s = null;
            for (Node t = tail; t != null && t != node; t = t.prev)
                if (t.waitStatus <= 0)
                    s = t;
        }
        if (s != null)
            // 唤醒后一个节点后但后一个节点不一定能够拿到锁资源 比如：非公平
            LockSupport.unpark(s.thread);
    }

    /**
     * 共享锁中的核心唤醒方法，主要做的事情就是唤醒下一个线程或者设置传播状态
     * 后继线程被唤醒后，会尝试获取共享锁，如果成功之后，则又会调用setHeadAndPropagate,将唤醒传播下去。
     * 这个函数的作用是保障在acquire和release存在竞争的情况下，保证队列中处于等待状态的节点能够有办法被唤醒。
     *
     * 在共享锁模式下，不论是setHeadAndPropagate方法还是releaseShared方法，都会调用到doReleaseShared，
     * 而且每个方法也可能有多个线程在调用。也就是说doReleaseShared方法会有多个线程在调用。
     *
     * 假如此时有多个线程进入到 int ws = h.waitStatus代码处，而其中一个线程先执行了
     * if (ws == Node.SIGNAL)的if条件，将头节点状态改为了0,那么剩下的线程就不能跳进int ws = h.waitStatus的if条件中，
     * 只能走到else if代码处，ws == 0条件满足，于是剩下的线程就去CAS竞争修改头节点状态为PROPAGATE（表示需要将唤醒动作向后继续传播）。
     * 修改成功的那个线程就跳到了if (h == head)代码处，进行下个判断逻辑，而再剩下修改失败的那些线程就让它们继续循环就行了
     * （剩下的那些线程会发现head节点此时已经变成了PROPAGATE状态，于是会在下一次循环的Node h = head代码处
     * 和if (h == head)代码处两次判断head指针是否指向了同一个节点（包括之前那个CAS修改成功的线程和执行唤醒
     * 动作的线程最后也会走到这里）。如果相同了，说明：
     * <1>可能是当前唤醒传播停止了（每个被唤醒的线程都可能会走入到本方法中的unparkSuccessor处
     * 唤醒下一个节点，相当于把唤醒动作“传播”下去。同时每次唤醒后会变更head指针，如果head不发生变动了，
     * 就说明唤醒传播停止了（注意上面所说的读写锁场景，也有可能是遇到了一个独占节点才停止的））；
     * <2>可能是将要唤醒下一个节点但还没唤醒前的瞬间
     * 不管是属于哪种情况，这些线程都可以退出了（该情况下只要等下一个节点唤醒并抢到锁后，还是会走到
     * 本方法里面的，也就是会将唤醒动作继续传播下去。但那个时候就不需要这些线程来操心了，只需要保证唤醒
     * 能一直传播下去就OK）
     *
     * 总结一下：因为head节点的状态为0就说明此时是一个中间过渡状态，最简单的情况下只有这个线程以及它所
     * 唤醒的下个线程们在一直传递地唤醒着，是不会走入到else if中来的。而如果有线程能走到这里，
     * 就说明此时在doReleaseShared方法有多个线程在同时调用着。PROPAGATE状态的出现，
     * 我认为是为了创造出一种区别于SIGNAL状态的另外一种状态（因为SIGNAL状态的含义定义死了就是代表后一个
     * 节点是阻塞状态，所以这里不能用SIGNAL状态来代替）。这个时候将head节点由原来的0置为PROPAGATE状态，
     * 以此来保证之前的那些线程也可以读取到此时旧的head节点状态是PROPAGATE，是<0的，从而可以调用到
     * doReleaseShared方法继续去唤醒下一个节点，也就是将唤醒动作传播下去
     */
    private void doReleaseShared() {
        for (;;) {
            Node h = head;
            // 保证同步队列中至少有两个节点（包括头结点），即至少含有一个真正在等待着的节点
            if (h != null && h != tail) {
                int ws = h.waitStatus;
                if (ws == Node.SIGNAL) {
                    if (!compareAndSetWaitStatus(h, Node.SIGNAL, 0))
                        continue;            // loop to recheck cases
                    //将头节点的state改为0成功的节点会去唤醒后继节点
                    unparkSuccessor(h);
                }
                else if (ws == 0 && !compareAndSetWaitStatus(h, 0, Node.PROPAGATE))
                    continue;                // loop on failed CAS
            }
            //如果head没有变化，跳出循环
            if (h == head)                   // loop if head changed
                break;
        }
    }

    /**
     * 这个函数做的事情有两件:
     * 1. 在获取共享锁成功后，设置head节点
     * 2. 根据调用tryAcquireShared返回的状态以及节点本身的等待状态来判断是否要需要唤醒后继线程。
     */
    private void setHeadAndPropagate(Node node, int propagate) {
        //h用来保存旧的head节点
        Node h = head;
        /*
         * 设置当前节点为新的头结点
         * 当前节点的waitStatus可能为0：加入队列后没有其他节点以当前节点为前驱节点
         * 当前节点的waitStatus可能为-1：加入队列后有其他节点以当前节点为前驱节点
         */
        setHead(node);
        /*
         * 如果仍然有多的锁(propagate的值是nonfairTryAcquireShared返回值)
         * 或者旧的头结点的 ws 小于0
         * 又或者新头结点的 ws 小于0，则唤醒后继节点
         * 判断为啥不是if(propagate > 0 && node.waitStatus!=0)?
         * 最开始的时候判断确实是这样？不过这里有一个bug 参考https://www.cnblogs.com/micrari/p/6937995.html
         */
        if (propagate > 0 //如果propagate > 0成立的话，说明还有剩余共享锁可以获取,propagate = 0才进行后续判断。
                || h == null //这里是不可能成立的
                || h.waitStatus < 0 //老的头结点状态PROPAGATE或SIGINAL
                || (h = head) == null //这里是不可能成立的
                || h.waitStatus < 0 //新的头结点状态PROPAGATE或SIGINAL
        ) {
            /*
             * 具体是否会调用doReleaseShared方法还需要判断node是最后一个节点或者node的下一个节点是
             * 共享节点的时候才去唤醒（判断s是否为null一方面也是为了后面判断s是否是共享节点时不会抛
             * 出空指针异常；但更重要的原因是因为如果node是CLH队列中的最后一个节点的话，这个时候虽然
             * 拿到的s是null，但如果此时有其他的线程在CLH队列中新添加了一个节点后，此处并不能及时感
             * 知到这个变化。于是此时也会走进doReleaseShared方法中去处理这种情况（当然，如果没有发生
             * 多线程插入节点的时候，多调用一次doReleaseShared方法也是无妨的，在该方法里面会过滤掉这
             * 种情况）。同时这里会特殊判断共享节点是因为CLH队列中可能会存在独占节点和共享节点共存的
             * 场景出现，也就是ReentrantReadWriteLock读写锁的场景。这里会一直传播唤醒共享节点直到遇
             * 到一个独占节点为止，后面的节点不管是独占或共享状态都不会再被唤醒了）
             */
            Node s = node.next;
            if (s == null || s.isShared())
                doReleaseShared();
        }
    }

    // Utilities for various versions of acquire 各种版本的acquire实用程序

    /**
     * 取消掉正在尝试去获取锁的节点
     */
    private void cancelAcquire(Node node) {
        // 节点不存在则忽略
        if (node == null)
            return;

        //置空关联线程
        node.thread = null;

        //剔除被cancel的前继node，找到未被取消的前继节点pred 可能是真正的等待节点也可能是头节点
        Node pred = node.prev;
        while (pred.waitStatus > 0)
            node.prev = pred = pred.prev;

        //必定是要被剔除的节点 可能是当前节点 也可能是当前节点的前面的某个节点，但肯定是被取消了的节点
        Node predNext = pred.next;

        // Can use unconditional write instead of CAS here.可以在这里使用无条件写入而不是 CAS。
        // After this atomic step, other Nodes can skip past us.在这个原子步骤之后，其他节点可以跳过我们。
        // Before, we are free of interference from other threads.之前，我们不受其他线程的干扰。
        node.waitStatus = Node.CANCELLED;

        // 如果当前节点是尾节点，将搜寻到的有效的前继节点设置为新的尾节点。
        // 更新失败的话，则进入else，如果更新成功，将tail的后继节点设置为null
        if (node == tail && compareAndSetTail(node, pred)) {
            //CAS设置尾部节点的下一个节点为null（失败就失败了，说明有新的节点加入队列）
            compareAndSetNext(pred, predNext, null);
        }
        //说明当前节点后有后继节点（两种原因：1.当前节点不是尾部节点 2.当前节点是尾部节点，但是上面的if中CAS设置自己为尾部节点失败）
        else {
            // If successor needs signal, try to set pred's next-link so it will get one. Otherwise wake it up to propagate.
            int ws;
            if (pred != head && //前驱有效节点不是头节点
                    // 如果当前节点不是head的后继节点，1:判断当前节点前驱节点的是否为SIGNAL，2:如果不是，则把前驱节点设置为SIGNAL看是否成功
                    ((ws = pred.waitStatus) == Node.SIGNAL || (ws <= 0 && compareAndSetWaitStatus(pred, ws, Node.SIGNAL))) &&
                    // 如果1和2中有一个为true，再判断前驱节点的线程是否为null
                    // 关联线程为null，要么是头结点要么是已经取消的节点 解释：虽然拿到pred的时候pred没有被取消，但是此刻pred可能已经被取消了
                    pred.thread != null
            ) {
                Node next = node.next;
                if (next != null && next.waitStatus <= 0)
                    //只是设置了有效的前置节点的后置节点，但并未设置当前取消节点的后继节点的前置节点。
                    //问题：设置next的前置是在哪里设置的？
                    //是别的线程做的。当别的线程在调用cancelAcquire()或者shouldParkAfterFailedAcquire()时，
                    //会根据prev指针跳过被cancel掉的前继节点，同时，会调整其遍历过的prev指针。
                    compareAndSetNext(pred, predNext, next);
            } else {
                //如果存在后继节点，这里说明无法给后继节点找到新的前驱节点（可能前驱节点是head，或者前驱节点失效了），直接唤醒后继节点
                //可能该唤醒操作时多余的，但是确保证了流程的一致性
                unparkSuccessor(node);
            }

            node.next = node; // help GC
        }
    }

    /**
     * 根据前置节点的状态决定是否能够安全的park当前节点
     */
    private static boolean shouldParkAfterFailedAcquire(Node pred, Node node) {
        //前置节点的状态
        int ws = pred.waitStatus;
        if (ws == Node.SIGNAL)
            //若前驱结点的状态是SIGNAL，意味着当前结点可以被安全地park
            return true;
        if (ws > 0) {
            //前驱节点状态如果被取消状态，将被移除出队列
            do {
                node.prev = pred = pred.prev;
            } while (pred.waitStatus > 0);
            pred.next = node;
        } else {
            //当前驱节点waitStatus为0时将前驱设置为SIGNAL状态，然后当前结点才可以被安全地park
            compareAndSetWaitStatus(pred, ws, Node.SIGNAL);
        }
        return false;
    }

    /**
     * 中断当前线程
     */
    static void selfInterrupt() {
        Thread.currentThread().interrupt();
    }

    /**
     * 阻塞当前节点，当节点被唤醒后会返回当前Thread是否被中断过
     * LockSupport.park 底层实现逻辑调用系统内核功能 pthread_mutex_lock 阻塞线程
     */
    private final boolean parkAndCheckInterrupt() {
        LockSupport.park(this);
        //返回当前线程是否被中断（会清除中断标识）
        return Thread.interrupted();
    }

    /*
     * Various flavors of acquire, varying in exclusive/shared and
     * control modes.  Each is mostly the same, but annoyingly
     * different.  Only a little bit of factoring is possible due to
     * interactions of exception mechanics (including ensuring that we
     * cancel if tryAcquire throws exception) and other control, at
     * least not without hurting performance too much.
     */

    /**
     * 已经在队列当中的Thread节点，准备阻塞等待获取锁
     */
    final boolean acquireQueued(final Node node, int arg) {
        //预设失败标识为true
        boolean failed = true;
        try {
            //预设失败标识为false
            boolean interrupted = false;
            for (; ; ) {
                //获取前置节点（从这里获取当前节点的前驱节点不会空指针）
                final Node p = node.predecessor();
                //只有前一个节点是头节点，也就是当前节点是实际上的第一个等待着的节点的时候才尝试获取资源（FIFO）
                //tryAcquire可能会抛出异常
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    //设置原头结点的下一个节点为null完成出队，方便GC
                    p.next = null; // help GC
                    failed = false;
                    //返回值代表当前线程是否被中断过，决定唤醒后的处理逻辑。
                    return interrupted;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 与acquireQueued逻辑相似，唯一区别节点是不在队列当中需要先进行入队操作
     */
    private void doAcquireInterruptibly(int arg)
            throws InterruptedException {
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                //获取前置节点（从这里获取当前节点的前驱节点不会空指针）
                final Node p = node.predecessor();
                //tryAcquire可能会抛出异常
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return;
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    //若线程被被中断过则抛出异常
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 独占模式定时获取
     */
    private boolean doAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.EXCLUSIVE);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head && tryAcquire(arg)) {
                    setHead(node);
                    p.next = null; // help GC
                    failed = false;
                    return true;
                }
                //用结束时间减去当前时间就是真正需要park的时间
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        //当剩余时间小于1000纳秒时我们任务不park性能更好
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 尝试获取共享锁
     */
    private void doAcquireShared(int arg) {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            boolean interrupted = false;
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        if (interrupted)
                            selfInterrupt();
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    interrupted = true;
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * 获取共享锁（若被中断则会抛出异常）
     */
    private void doAcquireSharedInterruptibly(int arg)
            throws InterruptedException {
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                /*
                 * 此处有几种可能：
                 * 1.刚入队，发现前置节点是头结点，此时头节点的waitStatus=0
                 * 2.已入队，发现前置节点是头结点，但获取资源失败，在shouldParkAfterFailedAcquire中将头节点waitStatus设置为-1
                 *   下一轮循环当前节点可能获取到资源进入代码块if (r >= 0) 或者 park住
                 * 3.入队后前置节点不是头结点，在shouldParkAfterFailedAcquire中将头节点waitStatus设置为-1
                 */
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    if (r >= 0) {
                        /*
                         * r大于等于0说明此时还有锁资源（等于0说明锁资源被当前线程拿走后就没了）,
                         * 设置自己为头节点，并且通知后面的节点也获取锁资源。
                         * 共享锁在前一个节点获取资源后，会通知后续的节点也一起来获取（能不能获取成功看情况）
                         */
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return;
                    }
                }
                if (shouldParkAfterFailedAcquire(p, node) &&
                        parkAndCheckInterrupt())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    /**
     * Acquires in shared timed mode.
     *
     * @param arg          the acquire argument
     * @param nanosTimeout max wait time
     * @return {@code true} if acquired
     */
    private boolean doAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (nanosTimeout <= 0L)
            return false;
        final long deadline = System.nanoTime() + nanosTimeout;
        final Node node = addWaiter(Node.SHARED);
        boolean failed = true;
        try {
            for (; ; ) {
                final Node p = node.predecessor();
                if (p == head) {
                    int r = tryAcquireShared(arg);
                    //大于等于0标识当前线程获取到了锁
                    if (r >= 0) {
                        setHeadAndPropagate(node, r);
                        p.next = null; // help GC
                        failed = false;
                        return true;
                    }
                }
                nanosTimeout = deadline - System.nanoTime();
                if (nanosTimeout <= 0L)
                    return false;
                if (shouldParkAfterFailedAcquire(p, node) &&
                        nanosTimeout > spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if (Thread.interrupted())
                    throw new InterruptedException();
            }
        } finally {
            if (failed)
                cancelAcquire(node);
        }
    }

    // 主要的对暴露的方法（子类重写实现自己的逻辑）

    /**
     * 尝试获取独占锁资源数（在子类中实现）
     */
    protected boolean tryAcquire(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 尝试释放独占锁资源数（在子类中实现）
     */
    protected boolean tryRelease(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 获取共享锁（在子类中实现）
     * 共享式地获取同步状态（同一时刻可以有多个线程同时获取到同步状态）
     * 1.当返回值大于0时，表示获取锁成功，且还有剩余锁资源；
     *
     * 2.当返回值等于0时，表示获取锁成功，但没有剩余锁资源；
     *
     * 3.当返回值小于0时，表示获取同步状态失败。
     */
    protected int tryAcquireShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 释放共享锁（在子类中实现）
     */
    protected boolean tryReleaseShared(int arg) {
        throw new UnsupportedOperationException();
    }

    /**
     * 当前线程是否持有独占锁
     */
    protected boolean isHeldExclusively() {
        throw new UnsupportedOperationException();
    }

    /**
     * acquire以独占exclusive方式获取资源。
     * 如果获取到资源，线程直接返回，否则进入等待队列，直到获取到资源为止，且整个过程忽略中断的影响。
     */
    public final void acquire(int arg) {
        if (!tryAcquire(arg) &&
                acquireQueued(addWaiter(Node.EXCLUSIVE), arg))
            //重置中断信号
            selfInterrupt();
    }

    /**
     * 获取独占锁，获取失败被阻塞，线程被中断直接抛出异常
     */
    public final void acquireInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (!tryAcquire(arg))
            doAcquireInterruptibly(arg);
    }

    /**
     * 获取独占锁，设置最大等待时间
     */
    public final boolean tryAcquireNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquire(arg) ||
                doAcquireNanos(arg, nanosTimeout);
    }

    /**
     * 释放独占模式持有的锁，并让后继节点获取执行机会
     */
    public final boolean release(int arg) {
        if (tryRelease(arg)) {
            Node h = head;
            //如果头部节点的waitStatus!=0说明有后继节点
            if (h != null && h.waitStatus != 0)
                unparkSuccessor(h);
            return true;
        }
        return false;
    }

    /**
     * 请求获取共享锁
     */
    public final void acquireShared(int arg) {
        if (tryAcquireShared(arg) < 0)
            doAcquireShared(arg);
    }

    /**
     * 尝试获取共享锁，获取失败被阻塞，线程被中断直接抛出异常
     */
    public final void acquireSharedInterruptibly(int arg)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        if (tryAcquireShared(arg) < 0)
            doAcquireSharedInterruptibly(arg);
    }

    /**
     * Attempts to acquire in shared mode, aborting if interrupted, and
     * failing if the given timeout elapses.  Implemented by first
     * checking interrupt status, then invoking at least once {@link
     * #tryAcquireShared}, returning on success.  Otherwise, the
     * thread is queued, possibly repeatedly blocking and unblocking,
     * invoking {@link #tryAcquireShared} until success or the thread
     * is interrupted or the timeout elapses.
     *
     * @param arg          the acquire argument.  This value is conveyed to
     *                     {@link #tryAcquireShared} but is otherwise uninterpreted
     *                     and can represent anything you like.
     * @param nanosTimeout the maximum number of nanoseconds to wait
     * @return {@code true} if acquired; {@code false} if timed out
     * @throws InterruptedException if the current thread is interrupted
     */
    public final boolean tryAcquireSharedNanos(int arg, long nanosTimeout)
            throws InterruptedException {
        if (Thread.interrupted())
            throw new InterruptedException();
        return tryAcquireShared(arg) >= 0 ||
                doAcquireSharedNanos(arg, nanosTimeout);
    }

    /**
     * Releases in shared mode.  Implemented by unblocking one or more
     * threads if {@link #tryReleaseShared} returns true.
     *
     * @param arg the release argument.  This value is conveyed to
     *            {@link #tryReleaseShared} but is otherwise uninterpreted
     *            and can represent anything you like.
     * @return the value returned from {@link #tryReleaseShared}
     */
    public final boolean releaseShared(int arg) {
        if (tryReleaseShared(arg)) {
            doReleaseShared();
            return true;
        }
        return false;
    }

    /**
     * 是否有等待的线程（头结点和尾节点不是同一节点就认为有）
     */
    public final boolean hasQueuedThreads() {
        return head != tail;
    }

    /**
     * Queries whether any threads have ever contended to acquire this
     * synchronizer; that is if an acquire method has ever blocked.
     *
     * <p>In this implementation, this operation returns in
     * constant time.
     *
     * @return {@code true} if there has ever been contention
     */
    public final boolean hasContended() {
        return head != null;
    }

    /**
     * Returns the first (longest-waiting) thread in the queue, or
     * {@code null} if no threads are currently queued.
     *
     * <p>In this implementation, this operation normally returns in
     * constant time, but may iterate upon contention if other threads are
     * concurrently modifying the queue.
     *
     * @return the first (longest-waiting) thread in the queue, or
     * {@code null} if no threads are currently queued
     */
    public final Thread getFirstQueuedThread() {
        // handle only fast path, else relay
        return (head == tail) ? null : fullGetFirstQueuedThread();
    }

    /**
     * 快速路径失败时调用的 getFirstQueuedThread 版本
     */
    private Thread fullGetFirstQueuedThread() {
        /*
         * The first node is normally head.next. Try to get its
         * thread field, ensuring consistent reads: If thread
         * field is nulled out or s.prev is no longer head, then
         * some other thread(s) concurrently performed setHead in
         * between some of our reads. We try this twice before
         * resorting to traversal.
         */
        Node h, s;
        Thread st;
        if (((h = head) != null && (s = h.next) != null &&
                s.prev == head && (st = s.thread) != null) ||
                ((h = head) != null && (s = h.next) != null &&
                        s.prev == head && (st = s.thread) != null))
            return st;

        /*
         * Head's next field might not have been set yet, or may have
         * been unset after setHead. So we must check to see if tail
         * is actually first node. If not, we continue on, safely
         * traversing from tail back to head to find first,
         * guaranteeing termination.
         */

        Node t = tail;
        Thread firstThread = null;
        while (t != null && t != head) {
            Thread tt = t.thread;
            if (tt != null)
                firstThread = tt;
            t = t.prev;
        }
        return firstThread;
    }

    /**
     * 判断当前线程是否在同步队列当中（从后往前检查）
     */
    public final boolean isQueued(Thread thread) {
        if (thread == null)
            throw new NullPointerException();
        for (Node p = tail; p != null; p = p.prev)
            if (p.thread == thread)
                return true;
        return false;
    }

    /**
     * Returns {@code true} if the apparent first queued thread, if one
     * exists, is waiting in exclusive mode.  If this method returns
     * {@code true}, and the current thread is attempting to acquire in
     * shared mode (that is, this method is invoked from {@link
     * #tryAcquireShared}) then it is guaranteed that the current thread
     * is not the first queued thread.  Used only as a heuristic in
     * ReentrantReadWriteLock.
     */
    final boolean apparentlyFirstQueuedIsExclusive() {
        Node h, s;
        return (h = head) != null &&
                (s = h.next) != null &&
                !s.isShared() &&
                s.thread != null;
    }

    /**
     * 判断当前节点是否有前驱节点（是否已经有排队的大哥）
     */
    public final boolean hasQueuedPredecessors() {
        // The correctness of this depends on head being initialized
        // before tail and on head.next being accurate if the current
        // thread is first in queue.
        Node t = tail; // Read fields in reverse initialization order
        Node h = head;
        Node s;
        //头结点不等于尾部节点 说明队列中最少有一个人在排队
        return h != t &&
                ((s = h.next) == null || s.thread != Thread.currentThread());
    }


    // Instrumentation and monitoring methods

    /**
     * Returns an estimate of the number of threads waiting to
     * acquire.  The value is only an estimate because the number of
     * threads may change dynamically while this method traverses
     * internal data structures.  This method is designed for use in
     * monitoring system state, not for synchronization
     * control.
     *
     * @return the estimated number of threads waiting to acquire
     */
    public final int getQueueLength() {
        int n = 0;
        for (Node p = tail; p != null; p = p.prev) {
            if (p.thread != null)
                ++n;
        }
        return n;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire.  Because the actual set of threads may change
     * dynamically while constructing this result, the returned
     * collection is only a best-effort estimate.  The elements of the
     * returned collection are in no particular order.  This method is
     * designed to facilitate construction of subclasses that provide
     * more extensive monitoring facilities.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            Thread t = p.thread;
            if (t != null)
                list.add(t);
        }
        return list;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire in exclusive mode. This has the same properties
     * as {@link #getQueuedThreads} except that it only returns
     * those threads waiting due to an exclusive acquire.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getExclusiveQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (!p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }

    /**
     * Returns a collection containing threads that may be waiting to
     * acquire in shared mode. This has the same properties
     * as {@link #getQueuedThreads} except that it only returns
     * those threads waiting due to a shared acquire.
     *
     * @return the collection of threads
     */
    public final Collection<Thread> getSharedQueuedThreads() {
        ArrayList<Thread> list = new ArrayList<Thread>();
        for (Node p = tail; p != null; p = p.prev) {
            if (p.isShared()) {
                Thread t = p.thread;
                if (t != null)
                    list.add(t);
            }
        }
        return list;
    }

    /**
     * Returns a string identifying this synchronizer, as well as its state.
     * The state, in brackets, includes the String {@code "State ="}
     * followed by the current value of {@link #getState}, and either
     * {@code "nonempty"} or {@code "empty"} depending on whether the
     * queue is empty.
     *
     * @return a string identifying this synchronizer, as well as its state
     */
    public String toString() {
        int s = getState();
        String q = hasQueuedThreads() ? "non" : "";
        return super.toString() +
                "[State = " + s + ", " + q + "empty queue]";
    }


    // Internal support methods for Conditions

    /**
     * 判断节点是否在同步队列中
     */
    final boolean isOnSyncQueue(Node node) {
        //快速判断1：节点状态为CONDITION或者节点没有前置节点肯定是在条件队列中
        //注：同步队列是有头节点的，而条件队列没有
        if (node.waitStatus == Node.CONDITION || node.prev == null)
            return false;
        //快速判断2：next字段只有同步队列才会使用，条件队列中使用的是nextWaiter字段
        if (node.next != null) // If has successor, it must be on queue
            return true;
        //上面如果无法判断则进入复杂判断
        return findNodeFromTail(node);
    }

    /**
     * 从同步队列尾部向前依次对比，查看当前节点是否在其中
     */
    private boolean findNodeFromTail(Node node) {
        Node t = tail;
        for (; ; ) {
            if (t == node)
                return true;
            if (t == null)
                return false;
            t = t.prev;
        }
    }

    /**
     * 将节点从条件队列当中移动到同步队列当中，等待获取锁
     */
    final boolean transferForSignal(Node node) {
        /*
         * 如果改变状态失败说明节点已被取消（使用CAS是为了防止节点正在取消因此的并发问题）
         */
        if (!compareAndSetWaitStatus(node, Node.CONDITION, 0))
            return false;

        /*
         * Splice onto queue and try to set waitStatus of predecessor to
         * indicate that thread is (probably) waiting. If cancelled or
         * attempt to set waitStatus fails, wake up to resync (in which
         * case the waitStatus can be transiently and harmlessly wrong).
         */
        //返回的是前驱节点
        Node p = enq(node);
        int ws = p.waitStatus;
        //如果前置节点被取消或者修改状态失败则直接唤醒当前节点，此时当前节点已经处于同步队列中，唤醒会进行锁获取或者正确的挂起操作
        if (ws > 0 || !compareAndSetWaitStatus(p, ws, Node.SIGNAL))
            LockSupport.unpark(node.thread);
        return true;
    }

    /**
     * 修改节点状态并加入同步队列
     * 返回true表示节点由中断加入同步队列，返回false表示由signal加入同步队列
     *
     * @param node the node
     * @return true if cancelled before the node was signalled
     */
    final boolean transferAfterCancelledWait(Node node) {
        if (compareAndSetWaitStatus(node, Node.CONDITION, 0)) {
            //进入CLH等待队列
            enq(node);
            return true;
        }
        /*
         * If we lost out to a signal(), then we can't proceed
         * until it finishes its enq().  Cancelling during an
         * incomplete transfer is both rare and transient, so just
         * spin.
         */
        while (!isOnSyncQueue(node))
            Thread.yield();
        return false;
    }

    /**
     * 全部释放占有的锁资源
     * 入参就是新创建的节点，即当前节点
     */
    final int fullyRelease(Node node) {
        boolean failed = true;
        try {
            int savedState = getState();
            if (release(savedState)) {
                failed = false;
                return savedState;
            } else {
                throw new IllegalMonitorStateException();
            }
        } finally {
            if (failed)
                node.waitStatus = Node.CANCELLED;
        }
    }

    // Instrumentation methods for conditions

    /**
     * Queries whether the given ConditionObject
     * uses this synchronizer as its lock.
     *
     * @param condition the condition
     * @return {@code true} if owned
     * @throws NullPointerException if the condition is null
     */
    public final boolean owns(ConditionObject condition) {
        return condition.isOwnedBy(this);
    }

    /**
     * Queries whether any threads are waiting on the given condition
     * associated with this synchronizer. Note that because timeouts
     * and interrupts may occur at any time, a {@code true} return
     * does not guarantee that a future {@code signal} will awaken
     * any threads.  This method is designed primarily for use in
     * monitoring of the system state.
     *
     * @param condition the condition
     * @return {@code true} if there are any waiting threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final boolean hasWaiters(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.hasWaiters();
    }

    /**
     * Returns an estimate of the number of threads waiting on the
     * given condition associated with this synchronizer. Note that
     * because timeouts and interrupts may occur at any time, the
     * estimate serves only as an upper bound on the actual number of
     * waiters.  This method is designed for use in monitoring of the
     * system state, not for synchronization control.
     *
     * @param condition the condition
     * @return the estimated number of waiting threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final int getWaitQueueLength(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitQueueLength();
    }

    /**
     * Returns a collection containing those threads that may be
     * waiting on the given condition associated with this
     * synchronizer.  Because the actual set of threads may change
     * dynamically while constructing this result, the returned
     * collection is only a best-effort estimate. The elements of the
     * returned collection are in no particular order.
     *
     * @param condition the condition
     * @return the collection of threads
     * @throws IllegalMonitorStateException if exclusive synchronization
     *                                      is not held
     * @throws IllegalArgumentException     if the given condition is
     *                                      not associated with this synchronizer
     * @throws NullPointerException         if the condition is null
     */
    public final Collection<Thread> getWaitingThreads(ConditionObject condition) {
        if (!owns(condition))
            throw new IllegalArgumentException("Not owner");
        return condition.getWaitingThreads();
    }

    /**
     * Condition implementation for a {@link
     * AbstractQueuedSynchronizer} serving as the basis of a {@link
     * Lock} implementation.
     *
     * <p>Method documentation for this class describes mechanics,
     * not behavioral specifications from the point of view of Lock
     * and Condition users. Exported versions of this class will in
     * general need to be accompanied by documentation describing
     * condition semantics that rely on those of the associated
     * {@code AbstractQueuedSynchronizer}.
     *
     * <p>This class is Serializable, but all fields are transient,
     * so deserialized conditions have no waiters.
     */
    public class ConditionObject implements Condition, java.io.Serializable {
        private static final long serialVersionUID = 1173984872572414699L;
        /**
         * 条件队列的第一个节点（和同步队列不同，该节点是真实节点）
         */
        private transient Node firstWaiter;
        /**
         * 条件队列的最后一个节点
         */
        private transient Node lastWaiter;

        /**
         * Creates a new {@code ConditionObject} instance.
         */
        public ConditionObject() {
        }

        // Internal methods

        /**
         * 入队到条件队列
         */
        private Node addConditionWaiter() {
            Node t = lastWaiter;
            // 若最后一个等待者是取消状态，清除出队。
            if (t != null && t.waitStatus != Node.CONDITION) {
                //从头部向后逐个断开被取消掉的节点（所有被取消的节点）
                unlinkCancelledWaiters();
                t = lastWaiter;
            }
            Node node = new Node(Thread.currentThread(), Node.CONDITION);
            if (t == null)
                firstWaiter = node;
            else
                t.nextWaiter = node;
            lastWaiter = node;
            return node;
        }

        /**
         * 该方法就是把一个有效节点从条件队列中删除并加入同步队列
         * 如果失败则会查找条件队列上等待的下一个节点直到队列为空
         */
        private void doSignal(Node first) {
            do {
                //条件队列头部调整，firstWaiter指针指向下一个节点
                if ((firstWaiter = first.nextWaiter) == null)
                    lastWaiter = null;
                //断开连接完成出队
                first.nextWaiter = null;
            } while (!transferForSignal(first) &&
                    (first = firstWaiter) != null);
        }

        /**
         * Removes and transfers all nodes.
         *
         * @param first (non-null) the first node on condition queue
         */
        private void doSignalAll(Node first) {
            lastWaiter = firstWaiter = null;
            do {
                Node next = first.nextWaiter;
                first.nextWaiter = null;
                transferForSignal(first);
                first = next;
            } while (first != null);
        }

        /**
         * Unlinks cancelled waiter nodes from condition queue.
         * Called only while holding lock. This is called when
         * cancellation occurred during condition wait, and upon
         * insertion of a new waiter when lastWaiter is seen to have
         * been cancelled. This method is needed to avoid garbage
         * retention in the absence of signals. So even though it may
         * require a full traversal, it comes into play only when
         * timeouts or cancellations occur in the absence of
         * signals. It traverses all nodes rather than stopping at a
         * particular target to unlink all pointers to garbage nodes
         * without requiring many re-traversals during cancellation
         * storms.
         */
        private void unlinkCancelledWaiters() {
            Node t = firstWaiter;
            //记录追踪到的未被取消的有效节点
            Node trail = null;
            while (t != null) {
                //记录当前节点的下一个节点
                Node next = t.nextWaiter;
                //如果当前节点是取消状态
                if (t.waitStatus != Node.CONDITION) {
                    //断开取消节点的下一个节点的指针
                    t.nextWaiter = null;
                    if (trail == null)
                        firstWaiter = next;
                    else
                        trail.nextWaiter = next;
                    //已经没有后续节点
                    if (next == null)
                        //追踪到的最新的有效节点就是尾节点
                        lastWaiter = trail;
                }
                //如果当前节点不是取消状态，追踪到的有效的节点就是当前节点
                else
                    trail = t;
                //下一个节点开始继续验证
                t = next;
            }
        }

        // public methods

        /**
         * 将等待时间最久的线程节点从条件队列移动到同步队列
         *
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        public final void signal() {
            //如果不是独占锁则抛出异常，说明条件队列只适用于独占锁
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignal(first);
        }

        /**
         * Moves all threads from the wait queue for this condition to
         * the wait queue for the owning lock.
         *
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        public final void signalAll() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            Node first = firstWaiter;
            if (first != null)
                doSignalAll(first);
        }

        /**
         * Implements uninterruptible condition wait.
         * <ol>
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * </ol>
         */
        public final void awaitUninterruptibly() {
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean interrupted = false;
            while (!isOnSyncQueue(node)) {
                LockSupport.park(this);
                if (Thread.interrupted())
                    interrupted = true;
            }
            if (acquireQueued(node, savedState) || interrupted)
                selfInterrupt();
        }

        /*
         * For interruptible waits, we need to track whether to throw
         * InterruptedException, if interrupted while blocked on
         * condition, versus reinterrupt current thread, if
         * interrupted while blocked waiting to re-acquire.
         */

        /**
         * Mode meaning to reinterrupt on exit from wait
         */
        private static final int REINTERRUPT = 1;
        /**
         * Mode meaning to throw InterruptedException on exit from wait
         */
        private static final int THROW_IE = -1;

        /**
         * Checks for interrupt, returning THROW_IE if interrupted
         * before signalled, REINTERRUPT if after signalled, or
         * 0 if not interrupted.
         * 如果在条件被发出信号之前发生中断，那么返回的结果是 "THROW_IE"，表示应该抛出中断异常（InterruptedException）。
         * 如果在条件被发出信号之后发生中断，那么返回的结果是 "REINTERRUPT"，表示应该重新中断当前线程。
         * 如果没有发生中断，那么返回的结果是 "0"，表示没有中断发生。
         */
        private int checkInterruptWhileWaiting(Node node) {
            return Thread.interrupted() ?
                    (transferAfterCancelledWait(node) ? THROW_IE : REINTERRUPT) :
                    0;
        }

        /**
         * Throws InterruptedException, reinterrupts current thread, or
         * does nothing, depending on mode.
         */
        private void reportInterruptAfterWait(int interruptMode)
                throws InterruptedException {
            if (interruptMode == THROW_IE)
                throw new InterruptedException();
            else if (interruptMode == REINTERRUPT)
                selfInterrupt();
        }

        /**
         * Implements interruptible condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled or interrupted.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * </ol>
         */
        public final void await() throws InterruptedException {
            //如果当前线程被中断则直接抛出异常
            if (Thread.interrupted())
                throw new InterruptedException();
            //把当前节点加入条件队列
            Node node = addConditionWaiter();
            //释放掉已经获取的独占锁资源 对于reentrantLock来说只有持有锁的线程才能去释放锁
            int savedState = fullyRelease(node);
            int interruptMode = 0;
            //如果不在同步队列中则不断挂起
            while (!isOnSyncQueue(node)) {
                //假如到条件队列中肯定不在同步队列中，但是被唤醒后就在同步队列中了（唤醒的线程拿到了当前节点把当前节点加入到了同步队列）
                LockSupport.park(this);
                //被中断的则直接跳出while循环
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            //节点已经条件满足被加入到了同步队列中 或者 被中断了
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            //走到这里说明已经成功获取到了独占锁，接下来就做些收尾工作
            if (node.nextWaiter != null) // clean up if cancelled
                //删除条件队列中被取消的节点
                unlinkCancelledWaiters();
            //根据不同模式处理中断
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
        }

        /**
         * Implements timed condition wait.实现定时条件等待。
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * 如果当前线程被中断了，抛出InterruptedException
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * 阻塞直到收到信号、被中断或超时
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * </ol>
         */
        public final long awaitNanos(long nanosTimeout)
                throws InterruptedException {
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    transferAfterCancelledWait(node);
                    break;
                }
                //park固定时间后会醒过来
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                //park一定时间后会醒过来，在算出的nanosTimeout就是一个负数了，到上面的nanosTimeout <= 0L就成立了会跳出while
                nanosTimeout = deadline - System.nanoTime();
            }
            //代码走到这里说明肯定在CLH队列中了
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return deadline - System.nanoTime();
        }

        /**
         * Implements absolute timed condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * <li> If timed out while blocked in step 4, return false, else true.
         * </ol>
         */
        public final boolean awaitUntil(Date deadline)
                throws InterruptedException {
            long abstime = deadline.getTime();
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (System.currentTimeMillis() > abstime) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                LockSupport.parkUntil(this, abstime);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        /**
         * Implements timed condition wait.
         * <ol>
         * <li> If current thread is interrupted, throw InterruptedException.
         * <li> Save lock state returned by {@link #getState}.
         * <li> Invoke {@link #release} with saved state as argument,
         *      throwing IllegalMonitorStateException if it fails.
         * <li> Block until signalled, interrupted, or timed out.
         * <li> Reacquire by invoking specialized version of
         *      {@link #acquire} with saved state as argument.
         * <li> If interrupted while blocked in step 4, throw InterruptedException.
         * <li> If timed out while blocked in step 4, return false, else true.
         * </ol>
         */
        public final boolean await(long time, TimeUnit unit)
                throws InterruptedException {
            long nanosTimeout = unit.toNanos(time);
            if (Thread.interrupted())
                throw new InterruptedException();
            Node node = addConditionWaiter();
            int savedState = fullyRelease(node);
            final long deadline = System.nanoTime() + nanosTimeout;
            boolean timedout = false;
            int interruptMode = 0;
            while (!isOnSyncQueue(node)) {
                if (nanosTimeout <= 0L) {
                    timedout = transferAfterCancelledWait(node);
                    break;
                }
                if (nanosTimeout >= spinForTimeoutThreshold)
                    LockSupport.parkNanos(this, nanosTimeout);
                if ((interruptMode = checkInterruptWhileWaiting(node)) != 0)
                    break;
                nanosTimeout = deadline - System.nanoTime();
            }
            if (acquireQueued(node, savedState) && interruptMode != THROW_IE)
                interruptMode = REINTERRUPT;
            if (node.nextWaiter != null)
                unlinkCancelledWaiters();
            if (interruptMode != 0)
                reportInterruptAfterWait(interruptMode);
            return !timedout;
        }

        //  support for instrumentation

        /**
         * Returns true if this condition was created by the given
         * synchronization object.
         *
         * @return {@code true} if owned
         */
        final boolean isOwnedBy(AbstractQueuedSynchronizer sync) {
            return sync == AbstractQueuedSynchronizer.this;
        }

        /**
         * Queries whether any threads are waiting on this condition.
         * Implements {@link AbstractQueuedSynchronizer#hasWaiters(ConditionObject)}.
         *
         * @return {@code true} if there are any waiting threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final boolean hasWaiters() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    return true;
            }
            return false;
        }

        /**
         * Returns an estimate of the number of threads waiting on
         * this condition.
         * Implements {@link AbstractQueuedSynchronizer#getWaitQueueLength(ConditionObject)}.
         *
         * @return the estimated number of waiting threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final int getWaitQueueLength() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            int n = 0;
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION)
                    ++n;
            }
            return n;
        }

        /**
         * Returns a collection containing those threads that may be
         * waiting on this Condition.
         * Implements {@link AbstractQueuedSynchronizer#getWaitingThreads(ConditionObject)}.
         *
         * @return the collection of threads
         * @throws IllegalMonitorStateException if {@link #isHeldExclusively}
         *                                      returns {@code false}
         */
        protected final Collection<Thread> getWaitingThreads() {
            if (!isHeldExclusively())
                throw new IllegalMonitorStateException();
            ArrayList<Thread> list = new ArrayList<Thread>();
            for (Node w = firstWaiter; w != null; w = w.nextWaiter) {
                if (w.waitStatus == Node.CONDITION) {
                    Thread t = w.thread;
                    if (t != null)
                        list.add(t);
                }
            }
            return list;
        }
    }

    /**
     * Setup to support compareAndSet. We need to natively implement
     * this here: For the sake of permitting future enhancements, we
     * cannot explicitly subclass AtomicInteger, which would be
     * efficient and useful otherwise. So, as the lesser of evils, we
     * natively implement using hotspot intrinsics API. And while we
     * are at it, we do the same for other CASable fields (which could
     * otherwise be done with atomic field updaters).
     */
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long stateOffset;
    private static final long headOffset;
    private static final long tailOffset;
    private static final long waitStatusOffset;
    private static final long nextOffset;

    static {
        try {
            stateOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("state"));
            headOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("head"));
            tailOffset = unsafe.objectFieldOffset
                    (AbstractQueuedSynchronizer.class.getDeclaredField("tail"));
            waitStatusOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("waitStatus"));
            nextOffset = unsafe.objectFieldOffset
                    (Node.class.getDeclaredField("next"));

        } catch (Exception ex) {
            throw new Error(ex);
        }
    }

    /**
     * CAS head field. Used only by enq.
     */
    private final boolean compareAndSetHead(Node update) {
        return unsafe.compareAndSwapObject(this, headOffset, null, update);
    }

    /**
     * CAS tail field. Used only by enq.
     */
    private final boolean compareAndSetTail(Node expect, Node update) {
        return unsafe.compareAndSwapObject(this, tailOffset, expect, update);
    }

    /**
     * CAS waitStatus field of a node.
     */
    private static final boolean compareAndSetWaitStatus(Node node,
                                                         int expect,
                                                         int update) {
        return unsafe.compareAndSwapInt(node, waitStatusOffset, expect, update);
    }

    /**
     * CAS next field of a node.
     */
    private static final boolean compareAndSetNext(Node node,
                                                   Node expect,
                                                   Node update) {
        return unsafe.compareAndSwapObject(node, nextOffset, expect, update);
    }
}
